The present invention relates to the decoding of multidimensional codes, such as are used in data transmission systems and in low-quantization-noise quantizers.
A multidimensional code is one in which each codeword is comprised of n elements, n.gtoreq.2. For example, each codeword of a four-dimensional code takes the form (.alpha.,.beta.,.gamma.,.delta.), where the elements .alpha., .beta., .gamma. and .delta. take on predetermined combinations of values. One particularly advantageous application for multidimensional coding is in the transmission of data over a so-called Gaussian channel--a communications channel in which the transmitted signals are corrupted by Gaussian noise. In such a system, each possible value of an input word (typically representing a plurality of data bits to be transmitted) is assigned to a different codeword of a pre-established n-dimensional codeword "alphabet." (In these applications the codewords are also referred to as "data symbols.") As each input word is applied at the transmitting end of the system, the assigned codeword is determined by table look-up or other means and a signal representing the codeword is applied to the channel. At the other end of the channel, the received, noise-corrupted codeword is decoded in a decoder, or decision-forming circuit. The function of the decoder is to form a (hopefully correct) decision as to what codeword was actually transmitted by finding the codeword within the alphabet to which the received noise-corrupted codeword is closest in n-space. The principal advantage of using multidimensional codes in such applications is that, as taught by C. E. Shannon in his classic paper "Communication in the Presence of Noise," Proc. IRE, Vol. 37, Jan., 1949, pp. 10-21, the probability of a decoding error at the receiver can be decreased by increasing the dimensionality of the codewords, given a particular channel and a fixed average power in the transmitted codewords. Examples of multidimensional data communications systems are those shown in U.S. Pat. No. 4,084,137 issued Apr. 11, 1978 to G. R. Welti hereby incorporated by reference.
Another advantageous application of multidimensional coding is in the quantization of analog signals into discrete quantization levels. An alphabet of n-dimensional codewords is pre-established, as before, and the samples of the analog input signal are divided into n-sample words. Each word is then applied to a decoder which finds that codeword within the alphabet to which the n-sample word is closest in n-space. Each of the n elements of the codeword is then used to represent the value of the corresponding analog sample. Advantageously, the average quantization error, i.e., the average difference between each analog sample and the codeword element which represents it, is decreased as the dimensionality of the code is increased. Multidimensional quantization is described more fully, for example, by A. Gersho in "Asymptatically Optimal Block Quantization," IEEE Trans. On Information Theory, Vol. IT-25, No. 4, July, 1979.